package com.company.algo.niuke;

/**接雨水问题【不会！】
 * https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
 解法1：暴力破解，
 纵向计算，如果当前是凹槽，计算凹槽上的雨水面积
 对于arr[i],left指针寻找左边最大高度的元素，right指针找右边最大高度的元素
 h=min(arr[left],arr[right])-arr[i]
 v=h*1
 解法2：优化后的双指针
 再暴力破解的基础上进行分析：
 定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。
 定理二：当我们从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，但right_max对它而言是不可信的。
                        （见下图，由于中间状况未知，对于left下标而言，right_max未必就是它右边最大的值）
                                    right_max
 left_max                              ——
    __                                |  |
   |  |__    __?????????????????????? |  |
 __|     |__|                       __|  |__
        left                      right
 定理三：当我们从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。

 对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，
 这时候，如果left_max<right_max成立，那么它就知道自己能存多少水了。
 无论右边将来会不会出现更大的right_max，都不影响这个结果。
 所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。
 */
public class MaxWater {
    //运行超时
    public long maxWater1 (int[] arr) {
        long res = 0;
        for (int i = 0; i < arr.length; i++) {
            int left = i, right = i;
            int leftMax = arr[i], rightMax = arr[i];
            while (left>=0){
                leftMax = Math.max(leftMax,arr[left]);
                left--;
            }
            while (right<arr.length){
                rightMax = Math.max(rightMax,arr[right]);
                right++;
            }
            res += (Math.min(leftMax,rightMax)-arr[i]);
        }
        return res;
    }

    public long maxWater2 (int[] arr) {
        int left = 0, right = arr.length-1;
        int leftMax = 0, rightMax = 0;
        long res = 0;
        while (left<=right){
            if (leftMax < rightMax){
                res += Math.max(0,leftMax-arr[left]);
                leftMax = Math.max(leftMax,arr[left]);
                left++;
            }
            else {
                res += Math.max(0,rightMax-arr[right]);
                rightMax = Math.max(rightMax,arr[right]);
                right--;
            }
        }
        return res;
    }
}
